package main

import "fmt"


type ListNode struct {
	Value int
	NextNode *ListNode
}

type BiTNode struct {
	data int
	lchild *BiTNode
	rchild *BiTNode
}

func main()  {
	//1.链表反转
	//初始化链表
	head_1 := &ListNode{Value: 1}
	node2_1 := &ListNode{Value: 2}
	node3_1 := &ListNode{Value: 3}
	head_1.NextNode = node2_1
	node2_1.NextNode = node3_1
	fmt.Println("初始链表为：")
	traver(head_1)
	fmt.Println("反转后的链表为：")
	traver(reverseList(head_1))

	//2.两个升序链表的合并
	//   2->5->8->10
	//   3->4->6->9
	//   2->3->4->5->6->8->9->10
	//初始化两个链表
	h1 := &ListNode{Value: 2}
	n11 := &ListNode{Value: 5}
	n12 := &ListNode{Value: 8}
	n13 := &ListNode{Value: 10}
	h1.NextNode = n11
	n11.NextNode =n12
	n12.NextNode = n13
	h2 := &ListNode{Value: 3}
	n21 := &ListNode{Value: 7}
	n22 := &ListNode{Value:9}
	n23 := &ListNode{Value: 11}
	h2.NextNode = n21
	n21.NextNode =n22
	n22.NextNode = n23
	fmt.Println("两个升序链表为：")
	traver(h1)
	traver(h2)
	fmt.Println("合并后的链表为：")
	h := merge(h1, h2)
	traver(h)

	//3.二叉树遍历
	//新建一个二叉树
	root := buildTree()
	//先序遍历
	fmt.Println("先序遍历序列：")
	PreOrder(root)
	fmt.Printf("\n")
	//中序遍历
	fmt.Println("中序遍历序列：")
	InOrder(root)
	fmt.Printf("\n")
	//后序遍历
	fmt.Println("后序遍历序列：")
	PostOrder(root)
	fmt.Printf("\n")
	//层序遍历
	fmt.Println("层序遍历序列：")
	LevelOrder(root)
	fmt.Printf("\n")

	//4.二叉树：找到两个叶子节点中最近的公共祖先节点
	var result []*BiTNode
	//result为保存叶子结点的切片
	result = Findchild(root)
	for i := 0; i < len(result); i++{
		for j := i + 1; j < len(result); j++{
			public := FindCommonAncestor(root, result[i], result[j])
			fmt.Printf("叶子结点%d与%d的公共节点为%d\n", result[i].data, result[j].data, public.data)
		}
	}

}

//遍历链表函数
func traver(head *ListNode){
	for head != nil{
		fmt.Printf("%d->", head.Value)
		head = head.NextNode
	}
	fmt.Println("nil")
}

//逆置链表函数
func reverseList(head *ListNode) *ListNode {
	p := head
	q := p.NextNode
	p.NextNode = nil
	for q != nil{
		r := q.NextNode
		q.NextNode = p
		p = q
		q = r
	}
	return p
}

//链表合并函数
func merge(head1 *ListNode, head2 *ListNode) *ListNode {
	var head *ListNode
	var p *ListNode
	for head1 != nil && head2 != nil{
		//处理头节点
		if head == nil{
			if head1.Value < head2.Value{
				head = head1
				p = head
				head1 = head1.NextNode
			}else {
				head = head2
				p = head
				head2 = head2.NextNode
			}
		}
		if head1.Value < head2.Value{
			p.NextNode = head1
			p = p.NextNode
			head1 = head1.NextNode
		}else{
			p.NextNode = head2
			p = p.NextNode
			head2 = head2.NextNode
		}
	}
	if head1 != nil{
		p.NextNode = head1
	}
	if head2 != nil{
		p.NextNode = head2
	}
	return head
}

//新建二叉树
func buildTree() *BiTNode{
	root := &BiTNode{data: 1}
	node2 := &BiTNode{data: 2}
	node3 := &BiTNode{data:3}
	root.lchild = node2
	root.rchild = node3
	node4 := &BiTNode{data: 4}
	node5 := &BiTNode{data: 5}
	node2.lchild = node4
	node2.rchild = node5
	return root
}
//遍历节点
func visit(node *BiTNode){
	fmt.Printf("%d", node.data)
}
//先序遍历
func PreOrder(T *BiTNode){
	if T != nil{
		visit(T)
		PreOrder(T.lchild)
		PreOrder(T.rchild)
	}
}
//中序遍历
func InOrder(T *BiTNode)  {
	if T != nil{
		InOrder(T.lchild)
		visit(T)
		InOrder(T.rchild)
	}
}
//后序遍历
func PostOrder(T *BiTNode)  {
	if T != nil{
		PostOrder(T.lchild)
		PostOrder(T.rchild)
		visit(T)
	}
}
//层次遍历
func LevelOrder(T *BiTNode)  {
	if T == nil{
		return
	}
	queue := []*BiTNode {T}
	for len(queue) > 0 {
		visit(queue[0])
		if queue[0].lchild != nil{
			queue = append(queue, queue[0].lchild)
		}
		if queue[0].rchild != nil{
			queue = append(queue, queue[0].rchild)
		}
		queue = queue[1:]
	}
}

//查找二叉树中任意两个节点的最近公共节点
func FindCommonAncestor(root, p, q *BiTNode) *BiTNode{
	if root == nil{
		return nil
	}
	if p == root || q == root{
		return root
	}
	left := FindCommonAncestor(root.lchild, p, q)
	right := FindCommonAncestor(root.rchild, p, q)
	if left != nil && right != nil {
		return root
	}
	if left != nil{
		return left
	}
	return right
}

//找叶子结点
func Findchild(root *BiTNode) []*BiTNode{
	var child []*BiTNode
	if root == nil{
		return child
	}
	if root.lchild == nil && root.rchild == nil{
		child = append(child, root)
	}
	left := Findchild(root.lchild)
	right := Findchild(root.rchild)
	child = append(child, left...)
	child = append(child, right...)
	return child
}